#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
    string _numTostr[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    void bfs(string &digits, int i, string &str, vector<string> &ret)
    {
        if (i == digits.size())
        {
            ret.push_back(str);
        }
        else
        {
            int num = digits[i] - '0';
            for (auto ch : _numTostr[num])
            {
                str += ch;
                bfs(digits, i + 1, str, ret);
                str.pop_back();
            }
        }
    }
    vector<string> letterCombinations(string digits)
    {
        vector<string> ret;
        string tmp;
        if (digits.size() == 0)
        {
            return ret;
        }
        int i = 0;
        bfs(digits, i, tmp, ret);
        return ret;
    }
};